//#include <stdio.h>
////pos1:起始位置
////pos2:中转位置
////pos3:目的位置
//void move(char pos1, char pos2)
//{
//    printf(" %c -> %c ", pos1, pos2);
//}
//
//int Hanoi(int n, char pos1, char pos2, char pos3)
//{
//    if (n == 1)
//    {
//        move(pos1, pos3);
//    }
//    else
//    {
//        Hanoi(n - 1, pos1, pos3, pos2);
//        move(pos1, pos3);
//        Hanoi(n - 1, pos2, pos1, pos3);
//    }
//}
//
//int main()
//{
//    Hanoi(1, 'A', 'B', 'C');
//    printf("\n");
//    Hanoi(2, 'A', 'B', 'C');
//    printf("\n");
//    Hanoi(3, 'A', 'B', 'C');
//    printf("\n");
//    return 0;
//}
/*
  int a = 10;
  原码：0 00000000000000000000001010
  反码：0 00000000000000000000001010
  补码：0 00000000000000000000001010

  int b = -10;
  原码：1 00000000000000000000001010
  反码：1 11111111111111111111110101
  补码：1 11111111111111111111110110

*/


//#include <stdio.h>
///*
//   &:按(2进制)位与          &&:逻辑与
//   |:按(2进制)位或          ||:逻辑或
//   ^:按(2进制)位异或  
//   ~:按(2进制)取反(单目)
//*/
//int main()
//{
//    int a = 6;
//    //00000000000000000000000000000110 —— 6的补码
//    int b = -7;
//    //10000000000000000000000000000111 —— -7的原码
//    //11111111111111111111111111111000 —— -7的反码
//    //11111111111111111111111111111001 —— -7的补码
//
//    int c = a & b; //a和b的补码的二进制位进行运算
//    //00000000000000000000000000000110 —— 6的补码
//    //11111111111111111111111111111001 —— -7的补码
//    //有0则0，同1才1。
//    //00000000000000000000000000000000 —— c的补码
//    //00000000000000000000000000000000 —— c的原码
//
//    int d = a | b;
//    //00000000000000000000000000000110 —— 6的补码
//    //11111111111111111111111111111001 —— -7的补码
//    //有1则1，同0才0。
//    //11111111111111111111111111111111 —— d的补码
//    //00000000000000000000000000000001 —— d的原码
//
//    int e = a ^ b;
//    //00000000000000000000000000000110 —— 6的补码
//    //11111111111111111111111111111001 —— -7的补码
//    //同0异1。
//    //11111111111111111111111111111111 —— e的补码
//    //00000000000000000000000000000001 —— e的原码
//
//    int f = ~a;
//    //00000000000000000000000000000110 —— 6的补码
//    //11111111111111111111111111111001 —— f的补码
//    //00000000000000000000000000000111 —— f的原码
//
//    return 0;
//}

//喝汽水，1瓶汽水1元，2个空瓶可以
//换一瓶汽水，给20元，可以喝多少汽水（编程实现）。
//#include <stdio.h>
//
//int main()
//{
//    printf("      *      \n");
//    printf("     ***     \n");
//    printf("    *****    \n");
//    printf("   *******   \n");
//    printf("  *********  \n");
//    printf(" *********** \n");
//    printf("*************\n");
//    printf(" *********** \n");
//    printf("  *********  \n");
//    printf("   *******   \n");
//    printf("    *****    \n");
//    printf("     ***     \n");
//    printf("      *      \n");
//    return 0;
//}

//求出0～100000之间的所有“水仙花数”并输出。

//“水仙花数”是指一个n位数，其各位数字的n次方之和确好等于该数本身，如 : 153＝1 ^ 3＋5 ^ 3＋3 ^ 3，则153是一个“水仙花数”。

//#include <stdio.h>
//#include <math.h>
//int main()
//{
//    int i = 0;
//    int j = 0;
//    int count = 0;
//    int sum = 0;
//    int a = 0;
//    int stemp = 0;
//    for (i = 1; i <= 100000; i++)
//    {
//        int n = i;
//        stemp = i;
//        count = 0;
//        sum = 0;
//        while (n)
//        {
//            n = n / 10;
//            count++;
//        }
//        for (j = 0; j < count; j++)
//        {
//            a = i % 10;
//            sum += pow(a, count);
//            i = i / 10;
//        }
//        if (stemp == sum)
//            printf("%d\n", stemp);
//        i = stemp;
//    }
////    return 0;
////}
//#include <stdio.h>
//#include <string.h>
//#include <math.h>
//
//void print_arr(int arr[], int sz)
//{
//    for (int i = 0; i < sz; i++)
//    {
//        printf("%d ", arr[i]);
//    }
//}
//
//int cmp_int(const void* p1, const void* p2)
//{
//    if (*(int*)p1 > *(int*)p2)
//    {
//        return 1;
//    }
//    else if (*(int*)p1 < *(int*)p2)
//    {
//        return -1;
//    }
//    else
//    {
//        return 0;
//    }
//}
//
////测试qsort，来排序整型数据。
//void test1()
//{
//    int arr[] = { 3,1,7,9,4,2,6,5,8,0 };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    qsort(arr, sz, sizeof(arr[0]), cmp_int);
//    print_arr(arr, sz);
//}
//
//struct Stu
//{
//    char name[20];
//    int age;
//};
//
////测试qsort，排序结构体数据
////比较两个结构体数据
//
//int cmp_stu_by_name(const void* p1, const void* p2)
//{
//    return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
//}
//
//int cmp_stu_by_age(const void* p1, const void* p2)
//{
//    return (((struct Stu*)p1)->age - ((struct Stu*)p2)->age);
//}
////按照名字排序
//void test2()
//{
//    struct Stu arr[] = { {"zhangsan",20},{"lisi",35},{"wangwu",18} };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);
//}
//
////按照年龄排序
//void test3()
//{
//    struct Stu arr[] = { {"zhangsan",20},{"lisi",35},{"wangwu",18} };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_age);
//}
//
//Swap( char* buf1 , char* buf2 , size_t width )
//{
//    int i = 0;
//    char temp = 0;
//    for (i = 0; i < width; i++)
//    {
//        temp = *buf1;
//        *buf1 = *buf2;
//        *buf2 = temp;
//    }
//}
//
//void bubble_sort(void* base,size_t sz,size_t width,int (*cmp)(const void* p1,const void* p2))
//{
//    //躺数
//    int i = 0;
//    for (i = 0; i < sz - 1; i++)
//    {
//        int j = 0;
//        for (j = 0; j < sz - 1 - i; j++)
//        {
//            //if (arr[j]>arr[j+1])
//            //比较两个元素
//            if(cmp( (char*)base+j*width,(char*)base+(j+1)*width )>0)
//            {
//                //交换两个函数
//                Swap( (char*)base + j * width, (char*)base + (j + 1) * width ,width );
//            }
//        }
//    }
//}
//
//int main()
//{
//    test2();
//
//    return 0;
//}

/*#include <stdio.h>
int main()
{
    //特例：sizeof（数组名）计算的是整个数组的大小
    //&数组名：整个数组的地址

    int a[] = { 1,2,3,4 };

    printf("%zd\n", sizeof(a));//16
    //数组名a单独放在sizeof内部，a表示整个数组，计算的是整个数组的大小，单位是字节

    printf("%zd\n", sizeof(a + 0));//4/8
    //这里的a是数组名表示首元素的地址，a+0还是首元素的地址

    printf("%zd\n", sizeof(*a));//4/8
    //这里的a是数组名表示首元素的地址，*a就是首元素，就是a[0]

    printf("%zd\n", sizeof(a + 1));//4/8

    printf("%zd\n", sizeof(a[1]));//4/8

    printf("%zd\n", sizeof(&a));//4/8
    //&a —— 这里的数组名a表示整个数组，&a是整个数组的地址
    //数组的地址也是地址，是地址就是4/8个字节的长度。

    printf("%zd\n", sizeof(*&a));//16

    printf("%zd\n", sizeof(&a + 1));//4/8
    //&a是数组的地址，&a+1是跳过整个数组后的那个位置的地址
    //&a+1是地址，是地址就是4/8个字节。

    printf("%zd\n", sizeof(&a[0]));//4/8

    printf("%zd\n", sizeof(&a[0] + 1));//4/8

    return 0;
}*/
/*
#include <stdio.h>
int main()
{
    char arr[] = { 'a','b','c','d','e','f' };

    printf("%d\n", sizeof(arr));// 6
    printf("%d\n", sizeof(arr + 0));// 4/8
    printf("%d\n", sizeof(*arr));// 1
    printf("%d\n", sizeof(arr[1]));// 1
    printf("%d\n", sizeof(&arr));// 4/8
    printf("%d\n", sizeof(&arr + 1));// 4/8
    printf("%d\n", sizeof(&arr[0] + 1));// 4/8

    return 0;
}*/
/*
#include <stdio.h>
#include <string.h>

int main()
{
    char arr[] = { 'a','b','c','d','e','f' };

    printf("%d\n", strlen(arr));// 随机值
    printf("%d\n", strlen(arr + 0));// 随机值
    printf("%d\n", strlen(*arr));
    //arr是数组首元素的地址，那么*arr就是首元素'a'，那么就是97，strlen会
    //认为97就是地址，最终程序就崩溃了
    printf("%d\n", strlen(arr[1]));// error
    printf("%d\n", strlen(&arr));// 随机值
    printf("%d\n", strlen(&arr + 1));// 随机值
    printf("%d\n", strlen(&arr[0] + 1));// 随机值

    return 0;
}
*/
/*
#include <stdio.h>
int main()
{
    char arr[] = "abcdef";

    printf("%zd\n", sizeof(arr));// 7
    //数组名单独放在sizeof内部，计算的是这个数组的大小

    printf("%zd\n", sizeof(arr + 0));// 4/8
    //arr + 0 是数组首元素的地址

    printf("%zd\n", sizeof(*arr));// 1
    //首元素地址解引用，那么*arr就是首元素

    printf("%zd\n", sizeof(arr[1]));// 1

    printf("%zd\n", sizeof(&arr));// 4/8

    printf("%zd\n", sizeof(&arr + 1));// 4/8

    printf("%zd\n", sizeof(&arr[0] + 1));// 4/8

    return 0;
}*/

/*
#include <stdio.h>
#include <string.h>

int main()
{
    char arr[] = "abcdef";

    printf("%d\n", strlen(arr));// 6
    //arr是首元素地址。然后它就从首元素地址开始往后找到\0为止。

    printf("%d\n", strlen(arr + 0));// 6
    //arr + 0 还是首元素地址

    printf("%d\n", strlen(*arr));// error
    //依旧是访问首元素，'a' —— 97

    printf("%d\n", strlen(arr[1]));// error

    printf("%d\n", strlen(&arr));// 6
    //数组的地址和数组首元素的地址是指向同一个位置的。
    //也是从第一个元素开始向后访问的。

    printf("%d\n", strlen(&arr + 1));// 随机值
    //跳过了整个数组。

    printf("%d\n", strlen(&arr[0] + 1));// 5
    //跳过了首元素。

    return 0;
}

*/

/*
#include <stdio.h>

int main()
{
    char* p = "abcdef";
    //p中放的是首元素的地址

    printf("%zd\n", sizeof(p));// 4/8

    printf("%zd\n", sizeof(p + 1));// 4/8

    printf("%zd\n", sizeof(*p));// 1

    printf("%zd\n", sizeof(p[0]));// 1

    printf("%zd\n", sizeof(&p));// 4/8
    //&p 是指针变量的地址(二级指针)

    printf("%zd\n", sizeof(&p + 1));// 4/8
    //&p是p的地址，&p+1是跳过p变量，指向了p的后面

    printf("%zd\n", sizeof(&p[0] + 1));// 4/8
    //b的地址

    return 0;
}*/
/*
#include <stdio.h>
int main()
{
    char* p = "abcdef";

    printf("%d\n", strlen(p));//6

    printf("%d\n", strlen(p + 1));// 5

    printf("%d\n", strlen(*p));// error

    printf("%d\n", strlen(p[0]));// error

    printf("%d\n", strlen(&p));// 随机值

    printf("%d\n", strlen(&p + 1));// 随机值

    printf("%d\n", strlen(&p[0] + 1));// 5

    return 0;
}*/
/*
#include <stdio.h>
int main()
{
    int a[3][4] = { 0 };
    printf("%zd\n", sizeof(a));// 48

    printf("%zd\n", sizeof(a[0][0]));// 4

    printf("%zd\n", sizeof(a[0]));// 16
    //a[0]是第一行的数组名

    printf("%zd\n", sizeof(a[0] + 1));// 4/8
    // &a[0][1]

    printf("%zd\n", sizeof(*(a[0] + 1)));// 4
    // a[0][1]

    printf("%zd\n", sizeof(a + 1));// 4/8
    //☆第二行的地址

    printf("%zd\n", sizeof(*(a + 1)));// 16

    printf("%zd\n", sizeof(&a[0] + 1));// 4/8
    //&a[0]是第一行的地址。那么+1就是第二行的地址。

    printf("%zd\n", sizeof(*(&a[0] + 1)));// 16

    printf("%zd\n", sizeof(*a));// 16

    printf("%zd\n", sizeof(a[3]));// 16
    //这个地方不会崩溃，因为sizeof内部的表达式是不会真实计算的，
    //a[3]其实是第四行的数组名。

    return 0;
    //
}*/


//#include <stdio.h>
//
////在X86环境下
////假设结构体的大小是20个字节
////程序输出的结果是啥？
//
//struct Test
//{
//    int Num;
//    char* pcName;
//    short sDate;
//    char cha[2];
//    short sBa[4];
//}*p = (struct Test*)0x100000;
//
//int main()
//{
//    printf("%p\n", p + 0x1);//p是结构体指针，+1就是跳过一个结构体，一个结构体是20个字节
//    //0x100014
//    printf("%p\n", (unsigned long)p + 0x1);//整数+1
//    //0x00100001
//    printf("%p\n", (unsigned int*)p + 0x1);//+1跳过一个unsigned int类型的变量，是4个字节
//    //0x00100004
//
//    return 0;
//}

//#include <stdio.h>
//#include <ctype.h>
//#include <string.h>
//#include <assert.h>
//
//size_t my_strlen(const char* str)
//{
//    if (*str != '\0')
//        return 1 + my_strlen(str + 1);
//    else
//        return 0;
//}
//
//int main()
//{
//    char arr[] = "abcdef";
//    size_t len = strlen(arr);
//    printf("%zd\n", len);
//
//    int ret = my_strlen(arr);
//    printf("%d\n", ret);
//    return 0;
//}
//#include <stdio.h>
//#include <string.h>
//
//int my_strcmp(const char* str1, const char* str2)
//{
//    while (*str1 == *str2)
//    {
//        if (*str1 == '\0')
//        {
//            return 0;
//        }
//        str1++;
//        str2++;
//    }
//    if (*str1 > *str2)
//        return 1;
//    else
//        return -1;
//}
//
//int main()
//{
//    char arr1[] = "abcdef";
//    char arr2[] = "abcde";
//    int ret = my_strcmp(arr1, arr2);
//    printf("%d\n", ret);
//
//    return 0;
//}

//#include <stdio.h>
//#include <string.h>
//#include <assert.h>
//
//const char* my_strstr(const char* str1, const char* str2)
//{
//    assert(str1 && str2);
//    const char* s1 = str1;
//    const char* s2 = str2;
//    const char* cur = str1;
//
//    if (*str2 == '\0')
//    {
//        return str1;
//    }
//
//    while (*cur)
//    {
//        s1 = cur;
//        s2 = str2;
//
//        while (*s1 && *s2 && *s1 == *s2)
//        {
//            s1++;
//            s2++;
//        }
//        if (*s2 == '\0')
//            return cur;
//        cur++;
//    }
//
//    return NULL;
//}
//
//int main()
//{
//    char arr[] = "abcdefabcdef";
//    char* p = "cdef";
//    const char* ret = my_strstr(arr, p);
//
//    if (ret == NULL)
//    {
//        printf("不存在");
//    }
//    else
//    {
//        printf("%s", ret);
//    }
//
//    return 0;
//}
//#include <stdio.h>
//#include <assert.h>
//#include <string.h>
//
//void* my_memmove(void* arr2, const void* arr1, size_t num)
//{
//    int i = 0;
//    assert(arr2 && arr2);
//    char* ret = arr2;
//    if (arr2 < arr1)//从前向后
//    {
//        while (num--)
//        {
//            *(char*)arr2 = *(char*)arr1;
//            arr2 = (char*)arr2 + 1;
//            arr1 = (char*)arr1 + 1;
//        }
//    }
//    else//从后到前
//    { 
//        while (num--)
//        {
//            *((char*)arr2 + num) = *((char*)arr1 + num);
//        }
//    }
//    return ret;
//}
//
//int main()
//{
//    int arr1[] = { 1,2,3,4,5,6,7,8,9,10 };
//    //将arr1中的3 4 5 6 7 拷贝放到arr2中
//    my_memmove(arr1 + 2, arr1, 20);
//    int i = 0;
//    for (i = 0; i < 10; i++)
//    {
//        printf("%d ", arr1[i]);
//    }
//    return 0;
////}
//#include <stdio.h>
//#include <stdlib.h>
//#include <math.h>
//
//int judge(unsigned int num)
//{
//    int i = 1;
//    for (i = 0; i <= 15; i++)
//    {
//        if ((num << (32 - 2 * i) | num >> 2 * i) > 0 && (num << (32 - 2 * i) | num >> 2 * i) <= 255)
//        {
//            return 1;
//        }
//    }
//    return 0;
//}//
//
//void find(unsigned int num)
//{
//    int m = -1;
//    int n = -1;
//    int i = 0;
//    for (i = 1; i <= pow(2, 32) - num; i++)
//    {
//        if (judge(num + i) && judge(i))
//        {
//            n = num + i;
//            break;
//        }
//    }
//    for (i = num - 1; i >= 0; i--)
//    {
//        if (judge(i) && judge(num - i))
//        {
//            m = i;
//            break;
//        }
//    }
//
//    if (n == -1 || m == -1)
//    {
//        printf("-2");
//    }
//    else
//    {
//        printf("%d,%d,%d", num, m, n);
//    }
//}
//
//int main()
//{
//    unsigned int k = 0;
//    scanf("%d", &k);
//
//    if (judge(k) == 1)
//    {
//        printf("-1");
//        return 0;
//    }
//    else
//    {
//        find(k);
//        return 0;
//    }
//}
//#include <stdio.h>
//#include <errno.h>
//#include <stdlib.h>
//
//int main()
//{
//    int* p = (int*)calloc(10, sizeof(int));
//    if (p = NULL)
//    {
//        perror("calloc");
//        return 1;
//    }
//    //使用空间
//    int i = 0;
//    for (i = 0; i < 10; i++)
//    {
//        printf("%d", p[i]);//*(p2+i)
//    }
//    //调整空间
//    int* ptr = (int*)realloc(p, 20 * sizeof(int));
//    if (ptr != NULL)
//    {
//        p = ptr;
//    }
//    //使用
//    //......
//
//
//    //释放
//    free(p);
//    p = NULL;
//    return 0;
//}

//#include <stdio.h>
//#include <stdlib.h>
//#include <stdbool.h>
//
//typedef struct GraphStruct
//{
//    int   vertex_num;//结点数(长和宽)
//    int   edge_num;//边数（元素个数）
//    int** edges;//矩阵上的具体元素值
//}GraphStruct;
//
//typedef struct GraphStruct* Graph;
//typedef unsigned int Vertex;
//
//typedef struct {
//    Vertex v;//结点1
//    Vertex w;//结点2
//    int    weight;//权重
//} Edge;
//
//void initGraph(Graph G)
//{
//    int i = 0;
//    int j = 0;
//    G->edges = (int**)malloc(G->vertex_num * sizeof(int*));
//    for (i = 0; i < G->vertex_num; i++)
//    {
//        G->edges[i] = (int*)malloc(G->vertex_num * sizeof(int));
//        for (j = 0; j < G->vertex_num; j++)
//        {
//            G->edges[i][j] = 0;
//        }
//    }
//}
//
//void readGraph(Graph G)
//{
//    int i = 0;
//    scanf("%d,%d", &(G->vertex_num), &(G->edge_num));
//    initGraph(G);
//    for (i = 0; i < G->edge_num; i++)
//    {
//        Edge e;
//        scanf("%u,%u,%u", &(e.v), &(e.w), &(e.weight));
//        G->edges[e.v][e.w] = e.weight;
//        G->edges[e.w][e.v] = e.weight;
//    }
//}
//
//bool dfs(Vertex start, Vertex* visited, Graph G, Vertex parent)
//{
//    visited[start] = 1;
//    for (Vertex end = 0; end < G->vertex_num; end++)
//    {
//        if (G->edges[start][end] != 0)
//        {
//            if (end == parent)
//                continue;
//            if (visited[end])
//                return true;
//            if (dfs(end, visited, G, start))
//                return true;
//        }
//    }
//    return false;
//}
//int main()
//{
//    Graph G = (Graph)malloc(sizeof(GraphStruct));
//    readGraph(G);
//
//    Vertex* visited = (Vertex*)calloc(G->vertex_num, sizeof(Vertex));
//
//    bool HaveCycle = false;
//    for (int start = 0; start < G->vertex_num; start++)
//    {
//        HaveCycle = dfs(start, visited, G, start);
//        if (HaveCycle)
//        {
//            HaveCycle = true;
//            break;
//        }
//        for (int i = 0; i < G->vertex_num; i++)
//            visited[i] = 0;
//    }
//
//
//    free(visited);
//    visited = NULL;
//
//    if (HaveCycle)
//        printf("yes\n");
//    else
//        printf("NO\n");
//
//    free(G);
//    G = NULL;
//
//    return 0;
//}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct GraphStruct
{
    int   vertex_num;//结点数(长和宽)
    int   edge_num;//边数（元素个数）
    int** edges;//矩阵上的具体元素值
}GraphStruct;

typedef struct GraphStruct* Graph;
typedef unsigned int Vertex;

typedef struct {
    Vertex v;//结点1
    Vertex w;//结点2
    int    weight;//权重
} Edge;

void initGraph(Graph G)
{
    int i = 0;
    int j = 0;
    G->edges = (int**)malloc(G->vertex_num * sizeof(int*));
    for (i = 0; i < G->vertex_num; i++)
    {
        G->edges[i] = (int*)malloc(G->vertex_num * sizeof(int));
        for (j = 0; j < G->vertex_num; j++)
        {
            G->edges[i][j] = 0;
        }
    }
}

void readGraph(Graph G)
{
    int i = 0;
    scanf("%d,%d", &(G->vertex_num), &(G->edge_num));
    initGraph(G);
    for (i = 0; i < G->edge_num; i++)
    {
        Edge e;
        scanf("%u,%u,%u", &(e.v), &(e.w), &(e.weight));
        G->edges[e.v][e.w] = e.weight;
    }
    for (i = 0; i < G->vertex_num; i++)
    {
        G->edges[i][i] = 1;
    }
}

void dfs(Graph G, int now, int last, int* dominate)
{
    for (int i = 0; i < G->vertex_num; i++)
    {
        if (G->edges[now][i] && i != last)//有一条边
        {
            if (dominate[i] == -1 || dominate[now] < dominate[i])
            {
                dominate[i] = now;
            }
            dfs(G, i, now, dominate);
        }
    }
}


int main()
{
    Graph G = (Graph)malloc(sizeof(GraphStruct));
    readGraph(G);

    int* dominate = (int*)malloc(G->vertex_num * sizeof(int));
    for (int i = 0; i < G->vertex_num; i++)
    {
        dominate[i] = -1;
    }


    dfs(G, 0, 0, dominate);

    for (int i = 1; i < G->vertex_num; i++)
    {
        if (dominate[i] != -1)
        {
            printf("%u#%u", dominate[i], i);
        }
    }



    free(G);
    G = NULL;
    free(dominate);
    dominate = NULL;

    return 0;
}